package ljl.alg.wangzheng_camp.round1.bfsdfs;

import java.util.ArrayList;
import java.util.List;

public class _37_solve_sudoku {
    
    /**
     * 背过第一个
     * */
    static class simple_dfs {
        boolean[][] lines = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][][] blocks = new boolean[3][3][9];
        boolean valid;
        List<int[]> dots = new ArrayList<>();
        public void solveSudoku(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.')
                        dots.add(new int[] {i, j});
                    else {
                        int d = board[i][j] - '0' - 1;
                        lines[i][d] = cols[j][d] = blocks[i / 3][j / 3][d] = true;
                    }
                }
            }
            dfs(board, 0);
        }
        void dfs(char[][] board, int pos) {
            if (pos == dots.size()) {
                valid = true;
                return;
            }
            int[] xy = dots.get(pos);
            int x = xy[0], y = xy[1];
            for (int i = 0; i < 9 && !valid; i++) {
                if (lines[x][i] || cols[y][i] || blocks[x / 3][y / 3][i]) continue;
                lines[x][i] = cols[y][i] = blocks[x / 3][y / 3][i] = true;
                board[x][y] = (char) (i + '0' + 1);
                dfs(board, pos + 1);
                lines[x][i] = cols[y][i] = blocks[x / 3][y / 3][i] = false;
            }
        }
    }
    
    /**
     * 位运算也没啥难的我们试试
     * */
    static class bitwise {
        int[] lines = new int[9];
        int[] cols = new int[9];
        int[][] blocks = new int[3][3];
        boolean valid;
        List<int[]> dots = new ArrayList<>();
        public void solveSudoku(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.')
                        dots.add(new int[] {i, j});
                    else {
                        flip(i, j, board[i][j] - '0' - 1);
                    }
                }
            }
            dfs(board, 0);
        }
        void dfs(char[][] board, int pos) {
            if (pos == dots.size()) {
                valid = true;
                return;
            }
            int[] xy = dots.get(pos);
            int x = xy[0], y = xy[1];
            int mask = ~(lines[x] | cols[y] | blocks[x / 3][y / 3]) & 0x1ff;
            for (; mask != 0 & !valid; mask &= mask - 1) {
                int d = Integer.bitCount((mask & -mask) - 1);
                flip(x, y, d);
                board[x][y] = (char) (d + '0' + 1);
                dfs(board, pos + 1);
                flip(x, y, d);
            }
        }
        void flip(int i, int j, int d) {
            lines[i] ^= 1 << d;
            cols[j] ^= 1 << d;
            blocks[i / 3][j / 3] ^= 1 << d;
        }
    }
    
    /**
     * 优化上面那个解法：如果某个位置只能放一个元素，就直接放进去，不递归放了
     * 这玩意有用吗？
     *
     * 快了 1-2ms 倒是
     * */
    static class youhua_2 {
        int[] lines = new int[9];
        int[] cols = new int[9];
        int[][] blocks = new int[3][3];
        boolean valid;
        List<int[]> spaces = new ArrayList<>();
    
        public void solveSudoku(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') flip(i, j, board[i][j] - '0' - 1);
                }
            }
            while (true) {
                boolean found = false;
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        if (board[i][j] == '.') {
                            int mask = ~(lines[i] | cols[j] | blocks[i / 3][j / 3]) & 0x1ff;
                            if ((mask & mask - 1) == 0) {
                                int d = Integer.bitCount(mask - 1);
                                flip(i, j, d);
                                board[i][j] = (char) (d + '0' + 1);
                                found = true;
                            }
                        }
                    }
                }
                if (!found) break;
            }
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') spaces.add(new int[]{i, j});
                }
            }
            dfs(board, 0);
        }
        void dfs(char[][] board, int pos) {
            if (pos == spaces.size()) {
                valid = true;
                return;
            }
            int[] xy = spaces.get(pos);
            int x = xy[0], y = xy[1];
            int mask = ~(lines[x] | cols[y] | blocks[x / 3][y / 3]) & 0x1ff;
            for (; mask != 0 && !valid; mask &= mask - 1) {
                int d = Integer.bitCount((mask & -mask) - 1);
                flip(x, y, d);
                board[x][y] = (char) (d + '0' + 1);
                dfs(board, pos + 1);
                flip(x, y, d);
            }
        }
        void flip(int x, int y, int d) {
            lines[x] ^= 1 << d;
            cols[y] ^= 1 << d;
            blocks[x / 3][y / 3] ^= 1 << d;
        }
    }
    
    /**
     * 这个写法感觉很简练的
     * 慢是慢了点，但是很优雅
     * */
    static class simple {
        public void solveSudoku(char[][] board) {
            dfs(board);
        }
    
        boolean dfs(char[][] board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') continue;
                    for (char k = '1'; k <= '9'; k++) {
                        if (validate(board, i, j, k)) {
                            board[i][j] = k;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
            return true;
        }
        boolean validate(char[][] board, int i, int j, int val) {
            for (int k = 0; k < 9; k++)
                if (board[i][k] == val) return false;
            for (int k = 0; k < 9; k++)
                if (board[k][j] == val) return false;
            int row = i / 3 * 3, col = j / 3 * 3;
            for (int k = row; k < row + 3; k++) {
                for (int l = col; l < col + 3; l++) {
                    if (board[k][l] == val) return false;
                }
            }
            return true;
        }
    }
    
}
